﻿#include "pch.h"

#include <iostream>
#include <vector>
#include <algorithm>

// 计算下一个排列
bool nextPermutation(std::vector<int>& arr) {
	// 找到最后一个升序的位置
	int i = arr.size() - 2;
	while (i >= 0 && arr[i] >= arr[i + 1]) {
		i--;
	}

	if (i < 0) {
		// 已经是最后一个排列
		return false;
	}

	// 找到大于arr[i]的最小元素
	int j = arr.size() - 1;
	while (arr[j] <= arr[i]) {
		j--;
	}

	// 交换arr[i]和arr[j]
	std::swap(arr[i], arr[j]);

	// 反转arr[i+1:]以获得下一个排列
	std::reverse(arr.begin() + i + 1, arr.end());

	return true;
}


TEST(Permutation, 1) {
	std::vector<int> arr = { 1, 2, 3 };

	do {
		for (int num : arr) {
			std::cout << num << " ";
		}
		std::cout << std::endl;
	} while (nextPermutation(arr));
}


// 生成数组的所有组合
std::vector<std::vector<int>> generateCombinations(const int& num) {
	int totalCombinations = 1 << num; // 2^n，代表所有可能的子集数量
	std::vector allCombinations(totalCombinations - 1, std::vector<int>());

	for (int i = 1; i < totalCombinations; ++i) {
		for (int j = 0; j < num; ++j) {
			if (i & (1 << j)) {
				allCombinations[i - 1].push_back(j);
			}
		}
	}

	return allCombinations;
}


TEST(Permutation, Combinations) {
	std::vector<std::vector<int>> allCombinations = generateCombinations(4);

	for (const std::vector<int>& combination : allCombinations) {
		for (int num : combination) {
			std::cout << num << " ";
		}
		std::cout << std::endl;
	}
}
